#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>



//struct Node* copyRandomList(struct Node* head)
//{
//    struct Node* cur = head;
//    while (cur)
//    {
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//        copy->val = cur->val;
//        copy->next = cur->next;
//        cur->next = copy;
//        cur = cur->next->next;
//    }
//    cur = head;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        if (cur->random == NULL)
//        {
//            copy->random = NULL;
//        }
//        else
//        {
//            copy->random = cur->random->next;
//        }
//        cur = cur->next->next;
//    }
//    struct Node* nwehead = NULL, * tail = NULL;
//    cur = head;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//        if (tail == NULL)
//        {
//            nwehead = tail = copy;
//        }
//        else
//        {
//            tail->next = copy;
//            tail = tail->next;
//        }
//        cur->next = next;
//        cur = next;
//    }
//    return nwehead;
//}



//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    struct ListNode* n1 = NULL, * n2 = head, * n3 = head->next;
//    while (n2)
//    {
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//        if (n3)
//            n3 = n3->next;
//    }
//    return n1;
//}


//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    struct ListNode* head = NULL, * tail = NULL;
//    while (list1 && list2)
//    {
//        if (list1->val < list2->val)
//        {
//            if (tail == NULL)
//            {
//                head = tail = list1;
//            }
//            else
//            {
//                tail->next = list1;
//                tail = tail->next;
//            }
//            list1 = list1->next;
//        }
//        else
//        {
//            if (tail == NULL)
//            {
//                head = tail = list2;
//            }
//            else
//            {
//                tail->next = list2;
//                tail = tail->next;
//            }
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//    return head;
//}



//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x)
//    {
//        struct ListNode* head1, * head2, * tail1, * tail2;
//        head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//        head2 = tail2 = (struct LsitNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                tail1->next = cur;
//                tail1 = tail1->next;
//            }
//            else
//            {
//                tail2->next = cur;
//                tail2 = tail2->next;
//            }
//            cur = cur->next;
//        }
//
//        tail1->next = head2->next;
//        tail2->next = NULL;
//        pHead = head1->next;
//        free(head1);
//        free(head2);
//        return pHead;
//    }
//};



struct ListNode* reserselist(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* nwehead = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = nwehead;
        cur = nwehead;
        cur = next;
    }
    return nwehead;
}

struct ListNode* middlenode(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

bool chkPalindrome(ListNode* head)
{
    struct ListNode* mid = middlenode(head);
    struct ListNode* rhead = reserselist(mid);
    while (head && rhead)
    {
        if (head->val != rhead->val)
            return false;
        head = head->next;
        rhead = rhead->next;
    }
    return true;
}